The present invention relates to an inference method and an inference apparatus for use with a knowledge base system, and in particular, to an inference method and an inference apparatus for use with a knowledge base system and knowledge base system support method and system using the inference method and apparatus.
Conventional knowledge base systems have been suffered with a problem of a low inference or reasoning speed. Processing to judge a rule condition takes a long period of time for determination of satisfaction or disatisfaction of the condition, which leads to inefficiency of the inference processing.
In order to overcome this difficulty, for a higher-speed reasoning, many knowledge engineering tools adopt a RETE algorithm or a TREAT algorithm to improve efficiency of the condition judge processing (pattern matching processing).
According to these algorithms, the judge processing is accomplished on a rule condition part based on a discrimination network in which each condition of the rule condition part is represented by a node.
With the provision of the discrimination network, identical conditions employed in a plurality of rules can be shared therebetween so as to express the conditions by a node. That is, the same condition judgement need not be duplicated.
In addition, intermediate results of condition judge operations conducted in the discrimination network can be memorized therein. Due to the memorized information, a condition judgement on data or a frame of data whose state has not been altered can be skipped. Namely, a result of the condition judgement can be replaced with an associated intermediate result retrieved from the discrimination network. Consequently, the condition judge processing is required to be executed only for data or a frame of data having a changed state thereby accomplishing the condition judgements on all condition parts of the respective rules.
In short, the operation range of the condition judgement can be limited, namely, the judge processing need be achieved only for data or a frame of data associated with the state which has been changed through an inference execution.
As described above, the rule condition parts are transformed into a discrimination network to keep therein intermediate results of condition judgements executed in the past. This consequently improves efficiency of the pattern matching operation and hence has been broadly used in many knowledge engineering tools.
A description of the conventional RETE algorithm is set forth an article entitled, RETE : A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem, Artificial Intelligence, Vol. 19, No. 1, pp. 17-37 (1982). For greater details regarding the TREAT algorithm, reference can be made to the article entitled, Treat: A Better Match Algorithm for AI Production Systems, AAAI-87, pp. 42-47 (1987).
In the conventional methods above, in a case of judgement on a complex condition related to many frames, there has been a problem of a considerable deterioration in the processing efficiency in association with the storage amount and range of the intermediate results of the condition judge processing
First, a description will be given of a difference of the storage range of intermediate results of the condition judgement between the two typical algorithms, namely, RETE and TREAT algorithms.
In general, conditions forming condition parts of rules can be classified into two types, namely, conditions astriding a plurality of frames and conditions which can be judged within a frame, which are called inter-conditions and intra-conditions, respectively. According to the RETE algorithm, a set of a frame satisfying an intra-condition and frames satisfying an inter-condition are stored as an intermediate result of a condition judge operation. On the other hand, in accordance with the TREAT algorithm, only the frame satisfying the intra-condition is memorized as an intermediate result of the condition judgement.
That is, the difference between these algorithms resides in whether or not the frames satisfying the inter-condition are to be stored.
As above, when the judgement is conducted depending on the RETE algorithm, there is stored a processing history up to a point where the inter-condition is satisfied. Consequently, for an inter-condition of which an intermediate result has been memorized, the condition judge processing is not necessary unless a state quantity of any frame related thereto has been altered. However, since an inter-condition is associated with a group of frames, a large amount of computations are required for storing and for controlling the intermediate processing results. In consequence, when the store information is not effectively utilized, the processing efficiency is considerably lowered.
In this regard, according to the TREAT algorithm, the processing history attained when the inter-condition is satisfied is not memorized, thereby coping with the problem above. On the other hand, however, the judgement of the inter-condition is required to be accomplished for each operation to compute an intermediate result. In consequence, in accordance with the TREAT algorithm, a problem of the RETE algorithm that the processing efficiency is remarkably deteriorated can be removed. However, conversely, for a problem which is effectively processed according to the RETE algorithm, the processing efficiency is considerably reduced when the TREAT algorithm is used.
The difference between the RETE and TREAT algorithms resides in the degree of the past processing results to be stored, namely, the length of the past processing results that are stored for future utilization. In consequence, the effectiveness of each algorithm is determined as follows. The algorithm selection is to be achieved depending on whether or not a system in which a re-execution of a condition judgement is achieved is more effective as compared with a system where the historical information is stored; or, conversely, whether or not a system using the results of the past processing develops a higher-speed processing as compared with a system where a condition judgement is re-executed.
However, the degree or amount of historical intermediate results of the condition judgements are decided according to characteristics of a problem associated therewith. That is, for a certain kind of problem, the intermediate results are preferably stored; whereas, for another kind of the problem, it is desirable not to memorize the intermediate results.
Furthermore, there may be considered a case where even in a rule condition description, for a portion (a sub-pattern) of a condition part, it is effective to memorize an intermediate result of processing, whereas a re-computation is favorable for the remaining portion thereof.
In consequence, in the method of the prior art wherein the storage range of the intermediate results of the condition judge processing is fixed, a rule description having an appropriate storage range of the intermediate results can be processed with a high efficiency, whereas the processing efficiency is conversely reduced for a rule description specified with an inappropriate storage range.
It is therefore an object of the present invention to provide an inference method and an inference apparatus for use with a knowledge base system and a support system and a support apparatus for use with a knowledge base using the inference method and apparatus, that avoids the disadvantages of the prior art.